Plus loin que la mémoisation : la tabulation

by serge-sans-paille

QuarksLab

PyConFR 2015, Pau

Qui suis-je ?



In [2]:

    
class Namek: pass
class Quarkslab: pass



In [3]:

    
class SergeSansPaille(Quarkslab, Namek):
    '''
    /me likes docstrings
    '''

    def work(self, *args, **kwargs):
        raise RuntimeError("not a good idea")

    def run(self):
        while 1:
            pass  # that's very fast!

    def hack(self, project):
        return project.name in ('pythran', 'llvm') or project.lang in ('python', 'c++')

Trou de mémoire



In [4]:

    
from functools import lru_cache

def fibo(n): # how no, not *you* again!
    return n if n < 2 else (fibo(n-1) + fibo(n-2))

@lru_cache(maxsize=20)
def memfibo(n): # how no, not *you* again!
    return n if n < 2 else (memfibo(n-1) + memfibo(n-2))



In [5]:

    
%timeit fibo(20)









    



100 loops, best of 3: 2.16 ms per loop



In [6]:

    
%timeit memfibo(20), memfibo.cache_clear()









    



10000 loops, best of 3: 68.9 µs per loop

Et si on poussait l'idée à l'extrême?



In [7]:

    
def P(v):
    c = 0
    while v:
        c += v&1
        v>>=1
    return c

Pm = lru_cache(maxsize=1<<16)(P)



In [8]:

    
l = list(range(1<<16))



In [9]:

    
%timeit [P(x) for x in l]









    



10 loops, best of 3: 102 ms per loop



In [10]:

    
%timeit [Pm(x) for x in l]









    



1 loops, best of 3: 92.7 ms per loop

Non, vraiment à l'extrême !



In [11]:

    
def tabulate(P):
    
    import numpy as np
    
    class Tabulated(object):
        
        def __init__(self):
            self.tabulated = np.array([P(x) for x in range(1<<16)],
                                      dtype=np.uint8)
    
        def __call__(self, x):
            return int(self.tabulated[x])
        
    return Tabulated()
    
Pt = tabulate(P)



In [12]:

    
%timeit [P(x) for x in l]









    



10 loops, best of 3: 100 ms per loop



In [13]:

    
%timeit [Pt(x) for x in l]









    



10 loops, best of 3: 21 ms per loop

Plus fort que la mémoisation : la tabulation

Précalculer tous les appels de la fonction, suivant le domaine d'entrée
Utiliser une Look Up Table pour remplacer l'appel de fonction

Problèmes

Définition du domaine d'entrée
Type de sortie
Taille de la LUT
Temps d'exécution

Annotations

On peut utiliser les annotations d'argument ppour calculer l'ensemble des valeurs possibles



In [14]:

    
from numpy import uint16, uint8

def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c

Compression

En un morceau

Compression de la LUT, en un bloc



In [15]:

    
def tabulate(P):
    import numpy, lz4
    
    class Tabulated(object):
        def __init__(self):
            self.tabulated = lz4.compress(
                numpy.array([P(x) for x in range(1<<16)],
                            dtype=numpy.uint8))
    
        def __call__(self, x):
            return int(lz4.decompress(self.tabulated)[x])
        
    return Tabulated()



In [16]:

    
Ptc = tabulate(P)



In [17]:

    
len(Pt.tabulated), len(Ptc.tabulated)









    Out[17]:





(65536, 616)



In [18]:

    
%timeit [P(x) for x in l]
%timeit [Pt(x) for x in l]
%timeit [Ptc(x) for x in l]









    



10 loops, best of 3: 100 ms per loop
10 loops, best of 3: 21 ms per loop
1 loops, best of 3: 387 ms per loop

→ Pas glop

Compression

par morceaux

tabulated = compress([xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx])

→

tabulateds = [ compress([xxxxxxxxxxxxxxxxxxxxxx]), ..., compress([xxxxxxxxxxxxxxxxxxxxxxxxx])]

En utilisant un algo qui décompresse vite, ça devrait passer!



In [19]:

    
def tabulate(P):
    import numpy, lz4

    size = 1 << 16
    chunk_size = 1 << 10
        
    class Tabulated(object):

        def __init__(self):
            self.tabulateds = [lz4.compress(numpy.array([P(x) for x in range(i*chunk_size, (i+1) * chunk_size)],
                                                        dtype=numpy.uint8))
                               for i in range(0, size, chunk_size)]

        def __call__(self, x):
            chunk_id = x // chunk_size
            return int(lz4.decompress(self.tabulateds[chunk_id])[x - chunk_id * chunk_size])
        
    return Tabulated()



In [20]:

    
Ptcm = tabulate(P)



In [21]:

    
len(Ptc.tabulated), sum(map(len,Ptcm.tabulateds)), len(Pt.tabulated)









    Out[21]:





(616, 8704, 65536)



In [22]:

    
%timeit [P(x) for x in l]
%timeit [Ptc(x) for x in l]
%timeit [Ptcm(x) for x in l]









    



10 loops, best of 3: 105 ms per loop
1 loops, best of 3: 385 ms per loop
10 loops, best of 3: 55.9 ms per loop

\o/

Et la sécurité dans tout ça ?

L'obfuscation, un moyen très utilisé pour « protéger » ses données ou ses algos (même en Python !)
Objectif : rendre une attaque en boîte blanche équivalente à une attaque en boîte noire

Attaque en boîte blanche



In [23]:

    
import inspect
print(inspect.getsource(P))









    



def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c



In [24]:

    
import dis
dis.dis(P)









    



  4           0 LOAD_CONST               1 (0)
              3 STORE_FAST               1 (c)

  5           6 SETUP_LOOP              34 (to 43)
        >>    9 LOAD_FAST                0 (v)
             12 POP_JUMP_IF_FALSE       42

  6          15 LOAD_FAST                1 (c)
             18 LOAD_FAST                0 (v)
             21 LOAD_CONST               2 (1)
             24 BINARY_AND
             25 INPLACE_ADD
             26 STORE_FAST               1 (c)

  7          29 LOAD_FAST                0 (v)
             32 LOAD_CONST               2 (1)
             35 INPLACE_RSHIFT
             36 STORE_FAST               0 (v)
             39 JUMP_ABSOLUTE            9
        >>   42 POP_BLOCK

  8     >>   43 LOAD_FAST                1 (c)
             46 RETURN_VALUE

Attaque en boîte noire



In [25]:

    
P(0), P(1), P(2), P(3), P(4), P(5), P(6) #...









    Out[25]:





(0, 1, 1, 2, 1, 2, 2)

Ou alors...



In [26]:

    
Pt.tabulated[:7]









    Out[26]:





array([0, 1, 1, 2, 1, 2, 2], dtype=uint8)

Tabulation $\simeq$ Boîte noire

L'attaquant a uniquement accès à la table des fonctions
Plus d'information sur la méchanique interne
On est sympa, on a fait l'explorationdes valeurs à sa place

→ Impossible de passer par un décorateur, ça suppose la connaissance du code de la fonction décorée



In [27]:

    
!cat P.py









    



from numpy import uint16, uint8
def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c



In [28]:

    
!python3 tabulate.py P --compress < P.py > Ptc.py



In [29]:

    
import Ptc
print(inspect.getsource(type(Ptc.P)))









    



class P :
	import numpy
	import lz4
	def __init__(self):
		self.cache = {}
		self.tabulated_results = [		 b'\x00\x04\x00\x00\x80\x00\x01\x01\x02\x01\x02\x02\x03\x04\x00D\x02\x03\x03\x04\x08\x00\x00\x0c\x00L\x03\x04\x04\x05\x10\x00\x04\x18\x00\x00\x1c\x00O\x04\x05\x05\x06 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x05\x06\x06\x07@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x06\x07\x07\x08\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x07\x08\x08\t\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x07\x08\x08\t\x08\t\t\n' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x06\x07\x07\x08\x07\x08\x08\t\x04\x00D\x08\t\t\n\x08\x00\x00\x0c\x00L\t\n\n\x0b\x10\x00\x04\x18\x00\x00\x1c\x00O\n\x0b\x0b\x0c \x00\r\x0c0\x00\x048\x00\x00<\x00O\x0b\x0c\x0c\r@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0c\r\r\x0e\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\r\x0e\x0e\x0f\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\r\x0e\x0e\x0f\x0e\x0f\x0f\x10' ,
]

	def __call__(self, *args): return P.numpy.frombuffer(P.lz4.decompress(self.tabulated_results[args[-1] // 1024]), dtype=P.numpy.uint8).reshape(-1).item(*args[:-1]+(args[-1] % 1024,))



In [30]:

    
%timeit [P(x) for x in l]









    



10 loops, best of 3: 106 ms per loop



In [31]:

    
%timeit [Ptc.P(x) for x in l]









    



1 loops, best of 3: 329 ms per loop

Avec un petit mécanisme de cache...



In [32]:

    
!python3 tabulate.py P --compress --cache-depth=2 < P.py > Ptcc.py



In [33]:

    
import Ptcc
l = list(range((1 << 16)))
%timeit [Ptcc.P(x) for x in l]









    



1 loops, best of 3: 277 ms per loop

Exemple concluant

Une des briques de l'algo MD5



In [34]:

    
!cat F.py









    



from numpy import uint8
def F(x:uint8, y:uint8, z:uint8):
        return (x & y) | ((~x) & z)



In [35]:

    
!python3 tabulate.py --compress --cache-depth=2 < F.py > Ftcc.py



In [36]:

    
import F, Ftcc
import itertools
l = range((1 << 4) )

%timeit [F.F(*args) for args in itertools.product(l,l,l)]









    



1000 loops, best of 3: 1.19 ms per loop



In [37]:

    
%timeit [Ftcc.F(*args) for args in itertools.product(l,l,l)]









    



100 loops, best of 3: 13.7 ms per loop

Kenavo

La boîte noire parfaite n'est pas un mythe

Les idées les plus stupides peuvent fonctionner
Avec un peu de siouxeries

Aller plus loin

Brancher ça sur Pythran pour générer les tabulations plus rapidement
S'inspirer de Blosc/Bcolz pour stocker les tables sur disques